題目

給定一個數獨遊戲，解了它!
相信大家都玩過，但還是附一下規則:

1. 同一列 1~9只能出現一次。
2. 同一行 1~9只能出現一次。
3. 在每個3x3的格子中，1~9只能出現一次。

解法

• 使用 Backtracking
  • 中文是回溯法，
  • 是一種枚舉多維度數值的方法。運用遞迴窮舉各個維度數值，產生所有可能的多維度數值。
  • 特色是一旦發現不正確的數值，就不遞迴，而回溯至上層，節省時間。
  • 大家熟知的經典問題：8皇后問題，能用Backtracking的概念去解。

Code 1

• 從左上角至右下角，遇到空的，就從那格去窮舉，找出能完成數獨的各格的值。每填一格值都會進行規則檢查，不符合就不會繼續遞迴下去，會回溯到上層。
• 寫完發現結果令人失望QQ，需要改善一下。

class Solution {
public:

    bool rule_check(vector<vector<char>>& board, int row, int col){
        int correct_count = 0; // there are three rules in Sudoku.

        //check row and column. When for-loop finish, only add 2.
        for(int i = 0; i < 9; i++){
            correct_count += board[i][col] == board[row][col];   
            correct_count += board[row][i] == board[row][col];
        }

        int ULC_row = (row/3)*3; // row index of upper left corner in sub-box.
        int ULC_col = (col/3)*3; // col index of upper left corner in sub-box.
        //check 3x3 sub-box. When for-loop finish, only add 1.
        for(int i = 0; i < 3; i++){
            for(int j = 0; j < 3; j++){
                correct_count += board[ULC_row + i][ULC_col + j] == board[row][col];
            }
        }

        return correct_count == 3; 
    }


    bool breaktracking(vector<vector<char>>& board, int row, int col){
        // should go to the next row?
        if(col == 9){
            row++;  
            col = 0;
        }

        // arrived bottom right corner?
        if(row == 9){
            return true; //done
        }

        // Is the cell empty? 
        // true: find appropriate value, false: go to the next cell.
        if(board[row][col]=='.'){
            //test all of possibility
            for(int val = 1; val < 10; val++){
                board[row][col] = '0' + val;
                // check and recursion.
                if(rule_check(board, row, col) && breaktracking(board, row, col + 1)){
                    return true;
                }
                //the val is invalid, so reset.
                board[row][col] = '.';
            }
        }
        else{
            return breaktracking(board, row, col + 1);
        }

        return false;
    }

    void solveSudoku(vector<vector<char>>& board) {
        breaktracking(board, 0, 0);
    }
};

Code 2

• 有個明顯可以改善的地方就是檢查的function。
  • 因為是暴力法，不優。
• 我們能建立一些bool array，去紀錄有訪問過的值。根據那3個規則，建立如下。
  • row與col各9
  • sub-box是9個3X3
  • 這3個array的最後一維度，表示不同數字1~9。
  • true代表visited

  visited_row[9][9]
  visited_col[9][9]
  visited_sub_box[3][3][9]
  

• 所以一開始，設這3個array每格都是false，並遍歷一次每格。先將數獨題目本身有數字的那些填true.
• 藉由維護這些array，我們能很快判斷是否違反規則。
• 基本上其他都沒改，已能節省很多時間!

class Solution {
public:
    bool visited_row[9][9] = {false};
    bool visited_col[9][9] = {false};
    bool visited_sub_box[3][3][9] = {false};

    bool rule_check(int row, int col, int val){
        return !visited_row[row][val] && !visited_col[col][val] && !visited_sub_box[row/3][col/3][val]; 
    }

    bool breaktracking(vector<vector<char>>& board, int row, int col) {
        // should go to the next row?
        if(col == 9){
            row++;  
            col = 0;
        }

        // arrived bottom right corner?
        if(row == 9){
            return true; //done
        }

        // Is the cell empty? 
        // true: find appropriate value, false: check next cells
        if(board[row][col]=='.'){
            //test all of possibility
            for(int val = 0; val < 9; val++){
                // check
                if(rule_check(row, col, val)) {
                    visited_row[row][val] = true;
                    visited_col[col][val] = true;
                    visited_sub_box[row/3][col/3][val] = true;

                    board[row][col] = '1' + val;

                    //recursive
                    if(breaktracking(board, row, col + 1)){
                        return true;
                    }

                    //the val is invalid, so reset.
                    board[row][col] = '.';
                    visited_row[row][val] = false;
                    visited_col[col][val] = false;
                    visited_sub_box[row/3][col/3][val] = false;
                }
            }
        }
        else{
            return breaktracking(board, row, col + 1);
        }

        return false;
    }

    void solveSudoku(vector<vector<char>>& board) {
        //init
        int q_val = 0;
        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++){
                if(isdigit(board[i][j])){
                    q_val = board[i][j] - '1';
                    visited_row[i][q_val] = true;
                    visited_col[j][q_val] = true;
                    visited_sub_box[i/3][j/3][q_val] = true;
                }
            }    
        }

        breaktracking(board, 0, 0);
    }
};